UVa/11375 - Matches/problem.cpp

   1 #pragma warning (disable:4786)
   2 #pragma warning (disable:4996)
   3 #include <time.h>
   4 #include <algorithm>
   5 #include <iostream>
   6 #include <sstream>
   7 #include <string>
   8 #include <vector>
   9 #include <queue>
  10 #include <stack>
  11 #include <set>
  12 #include <map>
  13 #include <cstdio>
  14 #include <cstdlib>
  15 #include <cctype>
  16 #include <cmath>
  17 #include <cassert>
  18 using namespace std;
  19
  20 #define REP(i,n) for(i=1; i<=(n); i++)
  21 #define REPO(i,n) for(int i=0; i<(n); i++)
  22 #define REPA(i,a,b) for(i=a; i<=(b); i++)
  23 #define min(a,b) ((a) < (b) ? (a) : (b))
  24 #define max(a,b) ((a) > (b) ? (a) : (b))
  25 #define init(a) (memset(a,0,sizeof(a)))
  26
  27 void open() {
  28         #ifndef ONLINE_JUDGE
  29                 freopen("test.in","rt",stdin);
  30                 freopen("test.out","wt",stdout);
  31         #endif
  32 }
  33
  34 const int MAX = 1000;
  35
  36 class HugeInt {
  37 public:
  38
  39         // vars
  40         char number[MAX];
  41         int length;
  42
  43         // constructors
  44         HugeInt() {
  45                 memset(number,0,sizeof(number));
  46                 length = 1;
  47         }
  48
  49         HugeInt(int n) {
  50                 *this = n;
  51         }
  52
  53         // operators
  54         // takes 'r' as right number and writes result to 'this'
  55         // *veryfied*
  56         HugeInt* operator= (const HugeInt* r) {
  57                 memset(number,0,sizeof(number));
  58                 strcpy(number,r->number);
  59                 length = r->length;
  60                 return this;
  61         }
  62
  63         // *veryfied*
  64         HugeInt* operator= (const int r) {
  65                 memset(number,0,sizeof(number));
  66                 sprintf(number,"%d",r);
  67                 length = strlen(number);
  68                 for (int i = 0; i < (length >> 1); i++) {
  69                         char c = number[i];
  70                         number[i] = number[length-i-1];
  71                         number[length-i-1] = c;
  72                 }
  73                 for (int j = 0; j < length; j++)
  74                         number[j] -= '0';
  75                 return this;
  76         }
  77
  78         // *veryfied*
  79         const HugeInt operator+ (const HugeInt& r) {
  80                 int n = max(length,r.length), carry = 0, k, i;
  81                 HugeInt theNew;
  82                 for (i = 0; i < n || carry; i++) {
  83                         k = number[i] + r.number[i] + carry;
  84                         theNew.number[i] = k % 10;
  85                         carry = k / 10;
  86                 }
  87                 theNew.length = i;
  88                 return theNew;
  89         }
  90
  91         // slightly veryfied
  92         void operator+= (const HugeInt& r) {
  93                 *this = *this + r;
  94         }
  95
  96         // *slightly veryfied*
  97         const HugeInt operator* (const int r) {
  98                 int i, k, carry = 0;
  99                 HugeInt theNew;
 100                 for (i = 0; i < length || carry; i++) {
 101                         k = number[i] * r + carry;
 102                         theNew.number[i] = k % 10;
 103                         carry = k / 10;
 104                 }
 105                 theNew.length = i;
 106                 return theNew;
 107         }
 108
 109         // *slightly veryfied*
 110         void operator*= (const int r) {
 111                 *this = *this * r;
 112                 //return this;
 113         }
 114
 115         // shifts number left by 'shift' positions
 116         // useful when multiplying two HugeInt's
 117         HugeInt operator<< (const int shift) {
 118                 int i;
 119                 HugeInt theNew;
 120                 // don't shift if number is 0 and there is no number
 121                 //if (length == 0 || length == 1 && number[0] == 0) return;
 122                 for (i = length - 1; i >= 0; i--)
 123                         theNew.number[i + shift] = number[i];
 124                 for (i = 0; i < shift; i++)
 125                         theNew.number[i] = 0;
 126                 theNew.length = length + shift;
 127                 return theNew;
 128         }
 129
 130         HugeInt operator* (HugeInt& r) {
 131                 int i;
 132                 HugeInt theNew = 0;
 133                 for (i = 0; i < length; i++)
 134                         theNew += (r << i) * number[i];
 135                 truncate(theNew);
 136                 return theNew;
 137         }
 138
 139         HugeInt operator*= (HugeInt& r) {
 140                 *this = *this * r;
 141                 return *this;
 142         }
 143
 144         int operator % (int r) {
 145                 int n = 0;
 146                 for (int i = length - 1; i >= 0; i--)
 147                         n = (n * 10 + number[i]) % r;
 148                 return n;
 149         }
 150
 151         int operator %= (int r) {
 152                 return (*this % r);
 153         }
 154
 155         HugeInt operator/ (int r) {
 156                 HugeInt I = 0;
 157                 int n = 0;
 158                 int j = 0;
 159                 for (int i = length - 1; i >= 0 || n >= r; i--) {
 160                         n = (n * 10 + number[i]);
 161                         I.number[j++] = n / r;
 162                         n %= r;
 163                 }
 164
 165                 // reverse string
 166                 for (int i = 0; i < j / 2; i++)
 167                         swap(I.number[i],I.number[j-i-1]);
 168                 I.length = j;
 169                 truncate(I);
 170
 171                 return I;
 172         }
 173
 174         HugeInt operator /= (int r) {
 175                 return (*this / r);
 176         }
 177
 178         // functions
 179         // *veryfied*
 180         void print() {
 181                 for (int i = length - 1; i >= 0; i--)
 182                         putchar(number[i] + '0');
 183         }
 184
 185         void truncate(HugeInt& n) {
 186                 for (int i = n.length - 1; i >= 0 && n.number[i] == 0; i--)
 187                         n.length--;
 188                 if (n.length == 0) {
 189                         n.number[0] = 0;
 190                         n.length = 1;
 191                 }
 192         }
 193
 194         HugeInt power(int p) {
 195                 HugeInt theNew = 1;
 196                 for (int i = 0; i < p; i++)
 197                         theNew *= *this;
 198                 return theNew;
 199         }
 200
 201         bool operator<(const HugeInt& rhs) {
 202                 if (this->length != rhs.length)
 203                         return this->length < rhs.length;
 204                 for (int i = 0; i < this->length; i++)
 205                         if (this->number[i] != rhs.number[i])
 206                                 return this->number[i] < rhs.number[i];
 207                 return false;
 208         }
 209
 210         bool isnull() {
 211                 if (length == 1 && number[0] == 0) {
 212                         return true;
 213                 }
 214                 return false;
 215         }
 216
 217 };
 218
 219 int M[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
 220 HugeInt DP[2001][2];
 221 HugeInt A[2001];
 222
 223 void precalc() {
 224         DP[0][1] = 1;
 225         for (int i = 1; i <= 2000; i++) {
 226                 DP[i][0] = 0;
 227                 DP[i][1] = 0;
 228                 if (i - M[0] >= 0) {
 229                         if (!DP[i - M[0]][0].isnull())
 230                                 DP[i][0] += DP[i - M[0]][0];
 231                         if (!DP[i - M[0]][1].isnull())
 232                                 DP[i][0] += DP[i - M[0]][1];
 233                 }
 234                 for (int j = 1; j < 10; j++) if (i - M[j] >= 0) {
 235                         if (!DP[i - M[j]][0].isnull())
 236                                 DP[i][1] += DP[i - M[j]][0];
 237                         if (!DP[i - M[j]][1].isnull())
 238                                 DP[i][1] += DP[i - M[j]][1];
 239                 }
 240                 //cout << i << ' ';
 241                 //DP[i][0].print();
 242                 //cout << ' ';
 243                 //DP[i][1].print();
 244                 //cout << endl;
 245         }
 246 }
 247
 248 void go() {
 249         A[0] = 0;
 250         for (int i = 1; i <= 2000; i++) {
 251                 A[i] = A[i - 1] + DP[i][1];
 252                 //cout << A[i].length << endl;
 253         }
 254 }
 255
 256 bool solve() {
 257         int n;
 258         if (scanf("%d",&n) != 1)
 259                 return false;
 260         if (n == 6){
 261                 printf("6\n");
 262                 return true;
 263         }
 264         HugeInt ans = A[n];
 265         HugeInt add = 1;
 266         if (n >= 6)
 267                 A[n] = A[n] + add;
 268         A[n].print();
 269         printf("\n");
 270         return true;
 271 }
 272
 273 int main() {
 274         open();
 275         precalc();
 276         go();
 277         while (solve());
 278
 279         return 0;
 280 }